package com.yiguang.algorithm.dp;

/*
 * 2.区间dp
 */
public class Section2Dp {

	/*
	 * 516. 最长回文子序列
	 */
	public int longestPalindromeSubseq(String s) {
		int length = s.length();
		int[][] dp = new int[length][length];
		int result = 1;
		for(int i=0; i<length; i++) {
			for(int j=length-1; j>=0; j--) {
				if(s.charAt(i)==s.charAt(j)) {
					dp[i][j] = dp[i-1][j-1]+2;
				}else {
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		return dp[0][length-1];
    }
}
